package com.mlh.binarytree;

/**
 * @author 缪林辉
 * @date 2024/8/26 14:59
 * @DESCRIPTION
 */
public class morris遍历 {
    //Morris遍历
    //假设来到当前节点cur，开始时cur来到头节点位置
    // 1）如果cur没有左孩子，cur向右移动(cur=cur.right)
    // 2）如果cur有左孩子，找到左子树上最右的节点mostRight:
        // a.如果mostRight的右指针指向空，让其指向cur,然后cur向左移动(cur = cur.left)
        // b.如果mostRight的右指针指向cur，让其指向null,然后cur向右移动(cur = cur.right)
    // 3）cur为空时,遍历停止
    public static void Morris(TreeNode root){
        if(root == null) return;
        TreeNode cur = root;
        while(cur != null){
            TreeNode MostRight = cur.left;
            if(MostRight != null){
                //寻找左子树最右节点
                while(MostRight.right != null && MostRight.right != cur){
                    MostRight = MostRight.right;
                }
                //找到了左子树最右节点
                if(MostRight.right == null){ //第一次找最右节点(cur被访问的第一次)
                    System.out.print(cur.val + " ");
                    MostRight.right = cur;
                    cur = cur.left;
                    continue;
                }else{                       //第二次找最右节点(cur被访问的第二次)
                    MostRight.right = null;
                }
            }
            System.out.print(cur.val + " ");
            cur = cur.right;
        }
    }

    public void morrisPractice(TreeNode root){
        if(root==null){
            return;
        }
        TreeNode cur=root;
        while (cur!=null){
            TreeNode MostRight = cur.left;
            if(MostRight!=null){
                //寻找左子树的最右节点
                while(MostRight.right!=null&&MostRight.right!=cur){
                    MostRight=MostRight.right;
                }
                if(MostRight.right==null){//第一次来到该节点
                    System.out.println(cur.val);
                    MostRight.right=cur;
                    cur=cur.left;//唯一cur向左移动，代表第一次遍历左子树
                    continue;
                }else{//第二次来到该节点
                    MostRight.right=null;
                }
            }
            System.out.println(cur.val);
            cur=cur.right;
        }
    }
}
